package william.heap;

/**
 * @author ZhangShenao
 * @date 2024/2/20
 * @description <a href="https://leetcode.cn/problems/kth-largest-element-in-an-array/">...</a>
 */
public class Leetcode215_数组中的第K大元素_堆排序 {
    /**
     * 采用堆排序
     * 利用shiftDown操作操作,自底向上建立大根堆
     * 将堆顶元素（数组0位置元素）与数组N-1位置元素交换,此时N-1位置元素即为第1大的元素
     * 对数组0位置元素进行shiftDown操作,维持大根堆
     * 上述过程持续k-1次
     * 最终堆顶元素（数组0位置元素）即为第K大元素,直接返回。
     * <p>
     * 时间复杂度O(N*logN)
     * 空间复杂度O(1)
     */
    public int findKthLargest(int[] nums, int k) {
        //边界条件校验
        if (nums == null || nums.length < k) {
            throw new IllegalArgumentException("invalid input!");
        }

        //自底向上,建立大根堆
        int heapSize = nums.length;
        buildMaxHeap(nums);

        //将堆顶元素与--heapSize的元素进行交换,此时heapSize位置的元素即为最大值
        //对刚交换过来的0位置的元素进行shiftDown操作,维持大根堆的性质
        //重复上述过程k次,最终heapSize位置的元素即为第k大的元素
        for (int i = 0; i < k; i++) {
            swap(nums, 0, --heapSize);
            shiftDown(nums, 0, heapSize);
        }

        return nums[heapSize];
    }

    /**
     * 自底向上,建立大根堆
     * 从末尾到开头遍历数组,进行shiftDown操作
     */
    private void buildMaxHeap(int[] nums) {
        int N = nums.length;
        for (int i = N - 1; i >= 0; i--) {
            shiftDown(nums, i, N);
        }
    }

    /**
     * 对数组nums中i位置的元素进行shiftDown操作,维持长度为heapSize的大根堆
     */
    private void shiftDown(int[] nums, int i, int heapSize) {
        //找到节点i的左、右子节点中的最大值,并尝试与节点i进行交换
        while (i < heapSize) {
            int left = i * 2 + 1;
            if (left >= heapSize) {  //无左子节点,直接终止
                break;
            }
            int maxIdx = left;
            int right = left + 1;
            if (right < heapSize && nums[right] > nums[left]) {
                maxIdx = right;
            }

            //节点i已经是最大值,无需交换,直接返回
            if (nums[i] >= nums[maxIdx]) {
                break;
            }

            //将节点i与最大值交换,并继续该操作
            swap(nums, i, maxIdx);
            i = maxIdx;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
